package Greed;

import java.util.Arrays;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class MaximizeSum {
    //k 次翻转操作后使数组和最大
    public int largestSumAfterKNegations(int[] nums, int k) {
        //m表示负数个数
        //m>k 把前k个小的负数转化为正数
        //m==k 把负数都化为正数
        //m<k 把m个负数都化为正数，m-k如果为偶数直接忽略，为奇数将当前的最小值变成负数
        int m=0;
        int min=Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<0){
                m++;
            }else{
                min=Math.min(min,Math.abs(nums[i]));
                break;
            }
            min=Math.min(min,Math.abs(nums[i]));
        }
        int sum=0;
        int i=0;
        if(m>k){
            for (int j = 0; j <nums.length ; j++) {
                if(j<k){
                    sum+=Math.abs(nums[j]);
                }else{
                    sum+=nums[j];
                }
            }
        }else if(m==k){
            for (int j = 0; j < nums.length; j++) {
                sum+=Math.abs(nums[j]);
            }
        }else {
            int n=k-m;
            for (int j = 0; j < nums.length; j++) {
                sum+=Math.abs(nums[j]);
            }
            if(n%2==1){
                sum-=min*2;
            }
        }
        return sum;
    }
    //按身高排序
}
